use std::collections::HashMap;
use regex::Regex;

pub fn count_provinces() -> String {
    let mut output = String::new();
    // parse ../district.json
    let json = include_str!("../district.json");
    let mut districts: HashMap<String, HashMap<String, Vec<String>>> = HashMap::new();
    let mut idx = "";
    for line in json.split('\n') {
        let re = Regex::new(r#""(.*?)""#).unwrap();
        let items: Vec<&str> = re.find_iter(line).map(|m| m.as_str().trim_matches('"')).collect();
        // println!("{:?}", items);
        if items.len() == 0 {
            continue;
        }
        if items.len() == 1 {
            idx = items[0];
            districts.entry(idx.to_string()).or_insert_with(HashMap::new);
            continue;
        }
        let key = items[0];
        if !districts.get(idx).unwrap().contains_key(key) {
            districts.get_mut(idx).unwrap().insert(key.to_string(), vec![]);
        }
        for v in items[1..].iter() {
            districts.get_mut(idx).unwrap().get_mut(key).unwrap().push(v.to_string());
        }
    }

    // println!("{:?}", districts);
    for i in 1..=5 {
        let input = districts.get(&i.to_string()).unwrap();
        // discretization
        let mut city: HashMap<String, usize> = HashMap::new();
        let mut cnt = 0;
        for (k, v) in input.iter() {
            if !city.contains_key(k) {
                // print!("{},", k);
                city.insert(k.to_string(), cnt);
                cnt += 1;
            }
            for i in v {
                if !city.contains_key(i) {
                    // print!("{},", i);
                    city.insert(i.to_string(), cnt);
                    cnt += 1;
                }
            }
        }
        // println!();
        // bfs
        let mut graph: Vec<Vec<usize>> = vec![vec![]; city.len()];
        for (k, v) in input.iter() {
            let u = city.get(k).unwrap();
            for i in v {
                let v = city.get(i).unwrap();
                // println!("{}:{}", k, i);
                graph[*u].push(*v);
                graph[*v].push(*u);
            }
        }
        let mut provinces = 0;
        let mut visited: Vec<bool> = vec![false; city.len()];
        for i in 0..city.len() {
            if visited[i] {
                continue;
            }
            provinces += 1;
            let mut queue: Vec<usize> = vec![i];
            visited[i] = true;
            while !queue.is_empty() {
                let u = queue.pop().unwrap();
                for &v in graph[u].iter() {
                    if !visited[v] {
                        visited[v] = true;
                        queue.push(v);
                    }
                }
            }
        }
        output.push_str(provinces.to_string().as_str());
        if i != 5 {
            output.push(',');
        }
    }
    output.to_string()
}
